Various cipher algorithms are used as a fundamental technique of a security system. The cipher algorithm may be divided into a public key cryptosystem and a common key cryptosystem. In the public key cryptosystem, different keys are used for encryption and decryption. In the public key cryptosystem, a encryption key, i.e. a public key is made public. In the public cryptosystem, a decryption key, i.e. a private key forms confidential information accessible only by the receiving party. On the other hand, in the common key cryptosystem, the same key, i.e. a common key is used for encryption and decryption. In the common key cryptosystem, safety is established by keeping the common key accessible only by a transmitting party and a receiving party and confidential to third parties.
The cipher algorithm of the common key cryptosystem, as compared with the cipher algorithm for the public key cryptosystem, has the advantage that its processing speed is higher and a more compact implementation is possible. Therefore, the cipher algorithm of the common key cryptosystem is widely used in small devices such as mobile phones and IC cards. Also, due to the high processing speed and the fact that information can be encrypted/decrypted in real time, the cipher algorithm of the common key cryptosystem is adopted also for information communication in a broadcasting field and a communication field.
The cipher algorithm of the common key cryptosystem is roughly divided into stream cipher and block cipher. The block cipher may be used for the common key cryptosystem to establish safety. In the block cipher, a plane text (text to be ciphered) is divided into segments (called the blocks) of fixed bit length, and then ciphered block by block. Note that a bit length of a block as a processing unit of ciphering is called a “block length”.
Various algorithms are known for the block cipher of the common key cryptosystem. Representative cipher algorithms include DES, AES, SC2000, MISTY (MISTY1, MISTY2), KASUMI and CAMELLIA. These cipher algorithms of the common key cryptosystem may be implemented as either hardware or software.
KASUMI is known as one of the algorithms of the block cipher. KASUMI is described in “Specification of the 3GPP Confidentiality and integrity Algorithms; Document 2: KASUMI Specification” (http://www.3gpp.org/ftp/Specs/archive/35_series/35.202/35202-700.zip). KASUMI is an algorithm having the private key of 128 bits and the block length of 64 bits. Specifically, KASUMI can generate a cipher text of 64 bits using the private key of 128 bits from a plane text of 64 bits. A round processing unit of KASUMI is described below.
FIG. 1 illustrates an example of the round processing unit for the encryption process of KASUMI. The round processing unit of KASUMI has a Feistel structure having a FO function and a FL function. KASUMI has the Feistel structure of 8 rounds. In the encryption process of KASUMI, a plane text P of 64 bits is input and a cipher text C of 64 bits is output. KLi, KOi, and KIi shown in FIG. 1 are extension keys generated from the private key of 128 bits. Each function is described in detail below.
FIG. 2 illustrates an example of the FOi function, where 1≦i≦8. A 32-bit input to the FOi function is divided into two data of 16 bits. The divided data are converted by exclusive disjunction and the FI function. KOij (1≦j≦3) and KIij (1≦j≦3) are the j-th 16-bit data from the left of the extension keys KOi and KIi, respectively.
FIG. 3 illustrates an example of the FIij function, where 1≦i≦8 and 1≦j≦3. A 16-bit input to the FIij function is divided into data of 9 bits on the left and data of 7 bits on the right. The divided data are converted by exclusive disjunction and two nonlinear functions S9 and S7. In FIG. 3, the term “zero-extended” indicates the conversion of the 7-bit data into the 9-bit data by adding zeros to its high-order two bits. The term “truncated” indicates the conversion of the 9-bit data into the 7-bit data by discarding its high-order two bits. The 7-bit data on the left of the extension key KIij is indicated as KIij1, and the 9-bit data on the right are indicated as KIij2.
FIG. 4 illustrates an example of the FLi function, where 1≦i≦8. A 32-bit input to the FLi function is divided into two data of 16 bits. The divided data are converted by the exclusive disjunction, AND gate and OR gate. KLij (1≦i≦8, 1≦j=2) indicates the j-th 16-bit data from the left of the extension key KLi.
The conventional compact implementation of the round processing unit of KASUMI is disclosed below.
FIGS. 5A and 5B illustrate an example of the compact implementation of the known technique FI function. FIG. 5A shows an example of a circuit that realizes the FO function. FIG. 5B shows an example of a circuit that realizes the FI function. Conventionally, the FI function may be realized with two cycles. In the circuit shown in FIG. 5B, an FI ½ module constituting only the upper half of the FI function may be implemented. In the circuit shown in FIG. 5B, the intermediate result of the first cycle is stored in a 16-bit register. Also, in the circuit shown in FIG. 5B, the intermediate result stored in the 16-bit register is input to an FI ½ module in the second cycle. As a result, the circuit shown in FIG. 5B realizes the FI function with two cycles in total.
The FI function executes the nonlinear conversion of 7 bits to 7 bits as S7 and the nonlinear conversion of 9 bits to 9 bits as S9. The FI function is known to include a part comparatively large in circuit size. The use of the FI ½ module leads to the advantage that the circuit size is reduced more than that in the case of implementing an entire FI function as it is.
Also, the FO function may be implemented on the basis of one FI function. As described above, the FO function has three FI functions. In the circuit shown in FIG. 5A, on the other hand, only one stage of the FI function may be implemented for the FO function. In the circuit shown in FIG. 5A, the bit width of the FO function is 32 bits, and therefore, the intermediate result is stored in a 32-bit register. In the circuit shown in FIG. 5A, the process is repeated in the next cycle with the intermediate result stored in the 32-bit register as an input. Thus, the circuit shown in FIG. 5A realizes the FO function.
The execution of the process in a plurality of cycles as described above eliminates the need of implementing plural FI functions. As a result, the circuit size of the round processing unit of KASUMI is advantageously reduced. Here, one stage of the FI function is processed with two cycles using the FI ½ module as described above. In other words, since the FI function is executed with two cycles, 6 cycles (=2 cycles×3 stages) is required to execute the FO function.
Conventionally, an example of the compact implement of the round processing unit of KASUMI requires 16 bits as an intermediate register for the FI function. Further, the known example requires 32 bits as an intermediate register for the FO function. In the known example, therefore, a total of 48 bits is required for the intermediate register. In following descriptions, the intermediate register for the FI function is referred to as FIreg and the intermediate register for the FO function as FOreg.
FIG. 6 illustrates an example of the round processing unit of the known technique KASUMI. In FIG. 6, RH, RL, LH and LL designate data registers for storing in-process results of the cipher text. When each of these registers has 16 bits, the size of the data registers is 64 bits in total.
The round processing unit shown in FIG. 6 includes a controller 31, a FL function 12, a FI ½ module 13, data registers 14a and 14b, intermediate registers 35a and 35b, XOR gates 36a and 36b, and selectors 37b, 37c, 37f, 37g, 37h, 37i and 37j. The data register 14a has 32 bits. The high-order 16 bits of the data register 14a correspond to RH, and the low-order 16 bits thereof to RL. The data register 14b has 32 bits. The high-order 16 bits of the data register 14b correspond to LH, and the low-order 16 bits thereof to LL. The intermediate register 35a has 16 bits and corresponds to FIreg, while the intermediate register 35b has 32 bits and corresponds to FOreg. The controller 31 controls the selectors 37b, 37c, 37f, 37g, 37h, 37i and 37j. 